# 给定一个含有 n 个正整数的数组和一个正整数 target 。
#  找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
#
#  示例 1：
# 输入：target = 7, nums = [2,3,1,2,4,3]
# 输出：2
# 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
#
#  示例 2：
# 输入：target = 4, nums = [1,4,4]
# 输出：1
#
#  示例 3：
# 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
# 输出：0
import sys
from typing import List


class Solution:
    def minSubArrayLen2(self, target: int, nums: List[int]) -> int:
        """
        解法二：滑动窗口
        :param target:
        :param nums:
        :return:
        """
        left, right, res, numLen = 0, 0, sys.maxsize, len(nums)
        tmpSum = 0  # 记录窗口内的元素和
        while right < numLen:
            tmpSum += nums[right]  # 当前窗口元素和小于target，窗口扩张
            while tmpSum >= target:  # 当前窗口元素和大于等于target，窗口持续收缩到元素和小于target
                res = min(res, right - left + 1)
                tmpSum -= nums[left]
                left += 1
            right += 1

        return res if res < sys.maxsize else 0

    def minSubArrayLen1(self, target: int, nums: List[int]) -> int:
        """
        解法一：前缀和（超时）
        :param target:
        :param nums:
        :return:
        """
        numLen = len(nums)
        prefixSums = [0] + [sum(nums[0:i + 1]) for i in range(numLen)]
        res = sys.maxsize
        for i in range(1, numLen + 1):
            for j in range(i):
                if prefixSums[i] - prefixSums[j] >= target:
                    res = min(res, i - j)
        return res if res < sys.maxsize else 0

    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        return self.minSubArrayLen2(target, nums)


if __name__ == "__main__":
    target, nums = 11, [1, 1, 1, 1, 1, 1, 1, 1]
    target, nums = 7, [2, 3, 1, 2, 4, 3]
    # target, nums = 4, [1, 4, 4]
    print(Solution().minSubArrayLen(target, nums))
